#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <string.h>

#include "heap.h"


#define TAMANIO_INICIAL 64

/************************************************
*	Definicion de los tipos de datos	*
************************************************/

struct heap{
    void  **vector;
    size_t tamanio;
    size_t cantidad;
    cmp_func_t cmp;
};

void heap_swap(heap_t *,size_t,size_t);

/************************************************
*		Primivivas del Heap		*
************************************************/
heap_t *heap_crear(cmp_func_t cmp)
{
    heap_t *heap = malloc(sizeof(heap_t));
    if(!heap)
        return NULL;

    heap->vector = calloc(TAMANIO_INICIAL,sizeof(void *));
    if(!heap->vector)
    {
        free(heap);
        return NULL;
    }

    heap->tamanio = TAMANIO_INICIAL;
    heap->cmp = cmp;
    heap->cantidad = 0;

    return heap;
}

void heap_destruir(heap_t *heap, void destruir_elemento(void *e))
{
    if(heap_esta_vacio(heap))
    {
        free(heap->vector);
        free(heap);
        return;
    }

    // Si existe la función destruir_elemento, la uso
    if(destruir_elemento)
    {

        while(!heap_esta_vacio(heap))
        {
            void *e = heap_desencolar(heap);

            if(!e)
            {
                fprintf(stderr, "ERROR: (destruir) e es NULL\n");
                continue;
            }

            destruir_elemento(e);
        }
    }

    free(heap->vector);
    free(heap);
    return;
}

bool heap_esta_vacio(const heap_t *heap)
{
    return (heap->cantidad == 0);
}

size_t heap_cantidad(const heap_t *heap)
{
    return heap->cantidad;
}

void *heap_ver_max(const heap_t *heap)
{
    if(heap_esta_vacio(heap))
        return NULL;

    return heap->vector[0];
}

size_t obtener_pos_padre(size_t hijo)
{
	return (hijo - 1) / 2;
}

bool up_heap(heap_t *heap,size_t pos_ingreso)
{
    if(heap_esta_vacio(heap))
        return true;

    void *e_nuevo = heap->vector[pos_ingreso];

    bool verificado = false;

    void *e_padre = NULL;

    do
    {
        size_t pos_padre = obtener_pos_padre(pos_ingreso);

        e_padre = heap->vector[pos_padre];

        // Controlo si hubo error
        if(!e_nuevo)
        {
            fprintf(stderr, "ERROR: e_nuevo es NULL\n");
            return false;
        }

        if(!e_padre)
        {
            fprintf(stderr, "ERROR: e_padre es NULL\n");
            return false;
        }

        if(heap->cmp(e_nuevo,e_padre) > 0)
        {
            // Swap
            heap_swap(heap,pos_ingreso,pos_padre);

            pos_ingreso = pos_padre;

            // Si no llegué a la posición 0, continuo
            if(pos_ingreso != 0)
                continue;
        }

        verificado = true;

    }while(!verificado);

    return true;
}

bool obtener_pos_del_hijo_mayor(heap_t *heap,size_t pos_padre,size_t fin,size_t *respuesta)
{
    size_t pos_izq = (pos_padre*2) +1;
    size_t pos_der = (pos_padre*2) +2;

    void *e_hijo_izq = NULL;

    // Verifico que pos_izq
    // no desborde el tope "fin"
    if(pos_izq <= fin)
        e_hijo_izq = heap->vector[pos_izq];

    void *e_hijo_der = NULL;

    // Verifico que pos_der
    // no desborde el tope "fin"
    if(pos_der <= fin)
        e_hijo_der = heap->vector[pos_der];

    // Verifico si el hijo_der es NULL
    // Como es un arbol completo
    // y se llena de izq a der
    // es la única caso posible
    if(e_hijo_izq && !e_hijo_der)
    {
        *respuesta = pos_izq;
        return true;
    }

    // Si los 2 son NULL, es hoja y se verifica antes
    // o los estoy forzando un tope con "fin"

    // Si ambos son verdaderos
    // los comparo
    if(heap->cmp(e_hijo_der,e_hijo_izq) > 0)
        *respuesta = pos_der;
    else
        *respuesta = pos_izq;

    return true;
}

bool elemento_en_pos_es_hoja(heap_t *heap,size_t pos_elemento,size_t fin)
{
    size_t pos_izq = (pos_elemento*2) +1;
    size_t pos_der = (pos_elemento*2) +2;

    void *hijo_izq = NULL;

    // Verifico que pos_izq
    // sea menor o igual al tope  "fin"
    if(pos_izq <= fin)
        hijo_izq = heap->vector[pos_izq];

    void *hijo_der = NULL;

    if(pos_der <= fin)
        hijo_der = heap->vector[pos_der];

    return (!hijo_der && !hijo_izq);
}

void heap_swap(heap_t *heap,size_t pos_a,size_t pos_b)
{
    void *aux = heap->vector[pos_a];
    heap->vector[pos_a] = heap->vector[pos_b];
    heap->vector[pos_b] = aux;

}

bool down_heap(heap_t *heap, size_t pos_inicial, size_t fin)
{
    void *e_desordenado = heap->vector[pos_inicial];

    bool verificado = false;

    void *e_hijo = NULL;

    do
    {
        // Es hoja
        if(elemento_en_pos_es_hoja(heap,pos_inicial,fin))
            break;

        size_t pos_hijo_mayor;

        if(!obtener_pos_del_hijo_mayor(heap,pos_inicial,fin,&pos_hijo_mayor))
        {
            fprintf(stderr, "ERROR: (down_heap) obtener_el_mayor_de_hijos devuelve falso\n");
            return false;
        }

        e_hijo = heap->vector[pos_hijo_mayor];

        // Verifico e
        // ya está verificado en el obtener_pos_del_hijo_mayor

        // Comparo
        if(heap->cmp(e_desordenado,e_hijo) < 0)
        {
            // Swap
            heap_swap(heap,pos_inicial,pos_hijo_mayor);

            pos_inicial = pos_hijo_mayor;

            continue;
        }

        verificado = true;

    }while(!verificado);

    return true;
}

bool heap_redimensionar(heap_t *heap, size_t tamanio_nuevo)
{
    void **vec = calloc(tamanio_nuevo,sizeof(void*));
    if(!vec)
    {
        fprintf(stderr, "ERROR: calloc devuelve NULL\n");
        return NULL;
    }

    for(unsigned i=0; i<heap->cantidad; i++)
        vec[i] = heap->vector[i];

    // Guardo la ref de vector en aux
    void **aux = heap->vector;

    // Actualizo vector con vec
    heap->vector = vec;

    // Actualizo el tamanio
    heap->tamanio = tamanio_nuevo;

    // Libero aux
    free(aux);
    return true;
}

bool heap_encolar(heap_t *heap, void *elem)
{
    unsigned pos;

    if(heap_esta_vacio(heap))
        pos = 0;
    else
        pos = heap->cantidad;

    //Controlo si tengo que redimensionar
    if(pos >= heap->tamanio)
        if(!heap_redimensionar(heap,heap->tamanio*2))
        {
            fprintf(stderr, "ERROR: heap_redimensionar devuelve falso\n");
            return false;
        }


    heap->vector[pos] = elem;

    if(!up_heap(heap,pos))
    {
        fprintf(stderr, "ERROR: up_heap devuelve falso\n");
        return false;
    }

    heap->cantidad++;
    return true;
}

void *heap_desencolar(heap_t *heap)
{
    if(heap_esta_vacio(heap))
        return NULL;

    // Obtengo el de mayor prioridad
    void *e = heap->vector[0];

    // Valido e
    if(!e)
    {
        fprintf(stderr, "ERROR: e es NULL\n");
        return NULL;
    }

    // Decremento la cantidad
    heap->cantidad--;

    if(heap_esta_vacio(heap))
        return e;

    // Controlar el invariante
    // Borro el último
    // y lo reemplazo
    // en el primer lugar
    void *ultimo = heap->vector[heap->cantidad];

    // Valido el último
    if(!ultimo)
    {
        fprintf(stderr, "ERROR: ultimo es NULL\n");
        return NULL;
    }

    heap->vector[0] = ultimo;

    if(!down_heap(heap,0,heap->cantidad-1))
    {
        fprintf(stderr, "ERROR: (desencolar) down_heap devuelve falso\n");
        return NULL;
    }

    // TODO: redimensionar hacia abajo

    return e;
}

void heap_sort(void *elementos[], size_t cant, cmp_func_t cmp)
{
    heap_t *heap = heap_crear(cmp);
    if(!heap)
        return;

    // Guardo el vector que me crea el heap
    void **aux = heap->vector;

    // Reemplazo con el vec elementos
    heap->vector = elementos;

    heap->cantidad = cant;

    heap_heapify(heap);

    size_t fin = cant-1;

    while(fin > 0)
    {

        heap_swap(heap,0,fin);

        fin--;

        if(!down_heap(heap, 0,fin))
        {
            fprintf(stderr, "ERROR: (heap_sort) down_heap devuelve falso\n");
            return;
        }
    }

    // Recupero el vecto
    heap->vector = aux;

    heap_destruir(heap,NULL);
}

void heap_heapify(heap_t *heap)
{
    int inicio = (heap->cantidad - 2 ) / 2;

    while(inicio >= 0)
    {
        if(!down_heap(heap,inicio,heap->cantidad-1))
        {
            fprintf(stderr, "ERROR: (heapify) down_heap devuelve falso\n");
            return;
        }
        inicio--;
    }
}

